package algorithm.problems.string;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by gouthamvidyapradhan on 09/03/2017.
 * Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
 * <p>
 * You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.
 * <p>
 * Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
 * <p>
 * For the last line of text, it should be left justified and no extra space is inserted between words.
 * <p>
 * For example,
 * words: ["This", "is", "an", "example", "of", "text", "justification."]
 * L: 16.
 * <p>
 * Return the formatted lines as:
 * [
 * "This    is    an",
 * "example  of text",
 * "justification.  "
 * ]
 * Note: Each word is guaranteed not to exceed L in length.
 */
public class TextJustification {
    public List<String> fullJustify(String[] words, int L) {
        int wCount = 0, charCount = 0;
        List<String> line = new ArrayList<>();
        List<String> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        for (int i = 0, l = words.length; i < l; i++) {
            String next = words[i];
            if ((L - (charCount + wCount)) >= next.length()) {
                line.add(next);
                charCount += next.length();
                wCount++;
            } else {
                //justify and add to list
                sb.append(line.get(0));
                StringBuilder space = new StringBuilder();
                if (line.size() > 1) {
                    int spaceCount = (L - charCount) / (wCount - 1);
                    int remaining = (L - charCount) % (wCount - 1);

                    for (int j = 0; j < spaceCount; j++)
                        space.append(' ');

                    for (int k = 1, kl = line.size(); k < kl; k++) {
                        sb.append(space);
                        if (remaining > 0) {
                            sb.append(' ');
                            --remaining;
                        }
                        sb.append(line.get(k));
                    }
                } else {
                    int balance = L - (charCount + (wCount - 1));
                    for (int j = 0; j < balance; j++)
                        sb.append(' ');
                }
                result.add(sb.toString());
                sb = new StringBuilder();
                line.clear();
                line.add(next);
                charCount = next.length();
                wCount = 1;
            }
        }
        if (!line.isEmpty()) {
            sb.append(line.get(0));
            for (int i = 1, l = line.size(); i < l; i++) {
                sb.append(' ');
                sb.append(line.get(i));
            }
        }
        int balance = L - (charCount + (wCount - 1));
        for (int i = 0; i < balance; i++)
            sb.append(' ');
        result.add(sb.toString());
        return result;
    }
}
